package com.lw.leetcode.arr.c;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * arr
 * c
 * 1611. 使整数变为 0 的最少操作次数
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/18 11:13
 */
public class MinimumOneBitOperations {
    public static void main(String[] args) {
        MinimumOneBitOperations test = new MinimumOneBitOperations();



        // 393
        int n = 2;

        // 393
//        int n = 333;

        // 756249599
//        int n = 1000000000;

        int i = test.minimumOneBitOperations(n);
        System.out.println(i);
    }


    /*
    二进制中 1 的位置映射的值，加减交替计算（九连环的模型）。

    1：这道题的模型就是九连环。

    2：创建模型， 若只有第 i 位为 1，其他的位置为 0, 则要反转 第i位，需要先把第 （i- 1）位反转位1，再反转第i位，再把（i- 1）位反转位0

    3：所以 f(n) = 2 * f(n - 1) + 1， 其中f(1) = 1;

    4：所以若只有第 i 位为 1，其他的位置为 0， 则f(n) = 2 ^ (i + 1) - 1 或者用位运算表示 f(n) =  (2 << i) - 1

    例如 n = 333， 则其二进制数字为： 101001101

    设置反转次数为 sum = 0;

    第8位：反转第8位的1，需要反转 511次， sum = sum + 511 = 511;

    第6位：但是 第6位已经有了 1，不需要再反转了，可以需要减去反转第6位的127次。 sum = sum - 127 = 384;

    第3位：而需要第6位起作用，其前面都不能为 1，只能为0，所以需要先把第3位的1，反转位0，反转第3位需要操作15次，sum = sum + 15 = 399;

    第2位：同理，若是操作第3位，第2位已经有了，不用再操作他的7次。所以 sum = sum - 7 = 392次。

    第0位：同理， 若是第2位起作用，其前面都必须为0，所以第0为先反转为0，需要操作一次。 sum = sum + 1 = 393

    以上规律，就是 二进制种，遇到 1 的时候，就可以 + - + - 的交替计算，加减的值为(2 << i) - 1计算。
     */
    public int minimumOneBitOperations(int n) {
        String s = Integer.toBinaryString(n);
        byte[] bytes = s.getBytes();
        int length = s.length();
        int sum = 0;
        boolean flag = true;
        for (int i = 0; i < length; i++) {
            if (bytes[i] == 49) {
                if (flag) {
                    sum += ((2 << (length - 1 - i)) - 1);
                } else {
                    sum -= ((2 << (length - 1 - i)) - 1);
                }
                flag = !flag;
            }
        }
        return sum;
    }
}
